
/**
 * 给定数组，从右下走到左上
 * 问能够拿到的分数，以及拿到最大分数的路径总数
 * 首先求一个最大值，比较简单的二维DP
 * 然后在已知最大值的情况下如何求得方案总数呢
 * 同样是DP，只是有限制条件
 * 当 D[i-1][j] + Board[i][j] == D[i][j] 时
 * 就将 F[i-1][j] 加到 F[i][j] 中，从i-1看就是刷表法，从ij看就是记忆化搜索
 * 刷表的话，无法决定Dij应有的值，所以从(n-1, m-1)递归进入即可
 * 标程是同时规划两个目标
 */

class Solution {
using llt = long long;
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size();
        int m = board[0].length();
        vector<vector<int>> D(n, vector<int>(m, -1));
        D[0][0] = 0;
        for(int i=0;i<n;++i)for(int j=0;j<m;++j){
            if(0 == i and 0 == j) continue;
            if('X' == board[i][j]) continue;
                        
            auto & dij = D[i][j];
            if(i > 0) chkmax(dij, D[i - 1][j]);
            if(j > 0) chkmax(dij, D[i][j - 1]);
            if(i > 0 and j > 0) chkmax(dij, D[i - 1][j - 1]);
            if(i + 1 != n or j + 1 != m and -1 != dij) chkaddAss(dij, board[i][j] - '0');
        }

        if(-1 == D[n - 1][m - 1]) return {0, 0};
        
        llt const MOD = 1E9 + 7;
        vector<vector<llt>> F(n, vector<llt>(m, -1LL));
        F[0][0] = 1;
        function<llt(int, int)> __dfs = [&](int x, int y)->llt{
            if(-1 != F[x][y]) return F[x][y];
            if('X' == board[x][y]) return F[x][y] = 0;

            auto curValue = 0;
            if(x + 1 != n or y + 1 != m) curValue = board[x][y] - '0';

            auto & ans = F[x][y];
            ans = 0;
            if(x > 0 and chkeq(D[x-1][y], curValue, D[x][y])){
                ans = (ans + __dfs(x - 1, y)) % MOD;
            }
            if(y > 0 and chkeq(D[x][y-1], curValue, D[x][y])){
                ans = (ans + __dfs(x, y - 1)) % MOD;
            }
            if(x > 0 and y > 0 and chkeq(D[x-1][y-1], curValue, D[x][y])){
                ans = (ans + __dfs(x - 1, y - 1)) % MOD;
            }
            return ans;
        };
        __dfs(n - 1, m - 1);
        return {D[n - 1][m - 1], (int)F[n - 1][m - 1]};
    }

    bool chkeq(llt a, llt b, llt c){
        if(-1 == a or -1 == b or -1 == c) return false;
        return a + b == c;
    }

    void chkmax(int & d, int a){
        if(-1 == a) return;
        if(-1 == d or d < a) d = a;
    }
    void chkaddAss(int & d, int v){
        assert(v != -1);
        if(-1 != d) d += v;
    }
};